struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

class Solution {
private:
  TreeNode *proc(TreeNode *now, int val) {
    if (!now) {
      return nullptr;
    }
    if (val > now->val) {
      TreeNode *p = new TreeNode;
      p->val = val;
      p->left = nullptr;
      p->right = nullptr;
      p->left = now;
      return p;
    }
    if (now->right == nullptr) {
      TreeNode *p = new TreeNode;
      p->val = val;
      p->left = nullptr;
      p->right = nullptr;
      now->right = p;
      return now;
    }
    now->right = proc(now->right, val);
    return now;
  }

public:
  TreeNode *insertIntoMaxTree(TreeNode *root, int val) {
    return proc(root, val);
  }
};
